题解 P4870 【[BalticOI 20A09 Day1]甲虫】

发表于 | 更新于

题意:有一只甲虫处于一根水平的树枝。因为他沉迷数学无法自拔，所以他觉得很像是在 $x$ 轴上。

在同一根树枝上，还有 $n$ 滴露水。每滴露水占用 $m$ 个单位的水分。相对于甲虫的位置，他们的坐标分别是 $x_1,x_2,\dots,x_n$。

显然，这一天将会骄阳似火。每过一个时间单位，就会有一个单位的水分从每一滴露水流失。这只甲虫受尽了烈阳的折磨，以至于每当它碰到一滴露水都能瞬间喝完。在每个时间单位中它能移动一个单位的距离。

所以你要写一个程序，根据露水的坐标，计算出甲虫最多能喝到的水。

$0 \le n \le 300,1 \le m \le 1,000,000,-10,000 \le x_1,x_2,\dots,x_n \le 10,000,$ 对于所有 $i \ne j,x_i \ne x_j$。

这道题应该一眼就能看出是区间$DP$，但是关键在于怎么写,我们用$f[i][j][0/1]$表示取完$i$~$j$之间的露水，停在$i$或$j$浪费的水分,因为露水水分不可能为负数，而走到后来可能行走路程$>m$，使得计算出的水分为负，所以我们要枚举取的总的露水数$p$（注意不是水分数）
于是我们可以列出状态转移方程：

$f[i][j][0]=min(f[i+1][j][0]+(p-len+1)\times(a[i+1]-a[i]),f[i+1][j][1]+(p-len+1)\times(a[j]-a[i]));$

$f[i][j][1]=min(f[i][j-1][1]+(p-len+1)\times(a[j]-a[j-1]),f[i][j-1][0]+(p-len+1)\times(a[j]-a[i]));$

$len$为$j-i+1$，即当前采集的露水数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
#include <bits/stdc++.h>
using namespace std;
inline int read(){
   int s=0,w=1;
   char ch=getchar();
   while(ch<'0'||ch>'9'){if(ch=='-')w=-1;ch=getchar();}
   while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
   return s*w;
}
int n,m,a[4000],f[400][400][2],t[400][400][2],ans;
int main(){
//	freopen("water.in","r",stdin);
//	freopen("water.out","w",stdout);
    n=read();m=read();
    for (int i=1;i<=n;i++) a[i]=read();
    a[++n]=0;//由于从0出发，故添加一个点为0
    sort(a+1,a+1+n);//排序应该不难理解
    int z=lower_bound(a+1,a+1+n,0)-a;//找出排序后0在的位置
    for (int p=1;p<=n;p++){//枚举p
        memset(f,0x3f,sizeof(f));
        f[z][z][0]=0;f[z][z][1]=0;//初始化
        for (int len=2;len<=p;len++)
            for (int i=1;i<=n-len+1;i++){
                int j=i+len-1;
                f[i][j][0]=min(f[i+1][j][0]+(p-len+1)*(a[i+1]-a[i]),f[i+1][j][1]+(p-len+1)*(a[j]-a[i])); 
                f[i][j][1]=min(f[i][j-1][1]+(p-len+1)*(a[j]-a[j-1]),f[i][j-1][0]+(p-len+1)*(a[j]-a[i]));//状态转移方程
                ans=max(ans,(len-1)*m-min(f[i][j][1],f[i][j][0]));统计答案
            }
    }
    cout<<ans;
}